package lanQiao;

import java.util.Scanner;

public class X16ToX8
{
	@SuppressWarnings("resource")
	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);

		for(int i=s.nextInt();i>0;i--)
		{
			char[] strs = s.next().toCharArray();
			
			int index = 0;
			String ans = "";
			
			switch(strs.length % 3)
			{
			case 1:
				ans += fexchange(0,0,strs[0]);
				index = 1;
				break;
			case 2:
				ans += fexchange(0,strs[0],strs[1]);
				index = 2;
				break;
			case 0:
				ans += fexchange(strs[0],strs[1],strs[2]);
				index = 3;
			}
			
			for(; index<strs.length; index+=3)
			{
				ans += exchange(strs[index],strs[index+1],strs[index+2]);
			}
			
			System.out.println(ans);
		}
	}
	
	private static String exchange(int a, int b, int c)
	{
		a = (a&0xf)+9*(a>>6);
		b = (b&0xf)+9*(b>>6);
		c = (c&0xf)+9*(c>>6);
		
		int i1 = a>>1;
		int i2 = (a&1)<<2|b>>2;
		int i3 = (b&3)<<1|c>>3;
		int i4 = c&7;
		
		return "" + i1 + i2 + i3 + i4;
	}
	
	private static String fexchange(int a, int b, int c)
	{
		a = (a&0xf)+10*(a>>6);
		b = (b&0xf)+10*(b>>6);
		c = (c&0xf)+10*(c>>6);
		
		return "" + ((a>>1)*1000 + ((a&1)<<2|b>>2)*100 + ((b&3)<<1|c>>3)*10 + (c&7));
	}
}
